//1192. 查找集群内的关键连接

//力扣数据中心有 n 台服务器，分别按从 0 到 n - 1 的方式进行了编号。它们之间以 服务器到服务器 的形式相互连接组成了一个内部集群，连接是无向的。
//用  connections 表示集群网络，connections[i] = [a, b] 表示服务器 a 和 b 之间形成连接。任何服务器都可以直接或者间接地通过网络到达任何其他服务器。
//关键连接 是在该集群中的重要连接，假如我们将它移除，便会导致某些服务器无法访问其他服务器。
//请你以任意顺序返回该集群内的所有 关键连接 。

//class Solution {
//public:
//    vector<int> low;
//    vector<int> dfn;
//    vector<vector<int>> edges;
//    vector<vector<int>> ans;
//    vector<int8_t> visited;
//    int time;
//
//    void tarjan(int node, int parent) {
//        time++;
//        low[node] = time;
//        dfn[node] = time;
//        visited[node] = true;
//
//        for (auto e : edges[node]) { // 访问node的每个邻接点
//            if (e == parent) {
//                continue;
//            }
//            if (!visited[e]) { // 没被访问
//                tarjan(e, node);
//                low[node] = min(low[e], low[node]);
//                if (low[e] > dfn[node]) { // node和e不在一个强联通分量里
//                    ans.push_back({ node, e });
//                }
//            }
//            else {
//                low[node] = min(low[node], dfn[e]);
//            }
//        }
//    }
//
//    vector<vector<int>> criticalConnections(int n, vector<vector<int>>& connections) {
//        low = vector<int>(n, -1);
//        dfn = vector<int>(n, -1);
//        visited = vector<int8_t>(n);
//        edges = vector<vector<int>>(n);
//        time = 0;
//        for (auto edge : connections) {
//            edges[edge[0]].emplace_back(edge[1]);
//            edges[edge[1]].emplace_back(edge[0]);
//        }
//
//        tarjan(0, -1);
//        return ans;
//    }
//};

//1568. 使陆地分离的最少天数

//给你一个大小为 m x n ，由若干 0 和 1 组成的二维网格 grid ，其中 1 表示陆地， 0 表示水。岛屿 由水平方向或竖直方向上相邻的 1 （陆地）连接形成。
//如果 恰好只有一座岛屿 ，则认为陆地是 连通的 ；否则，陆地就是 分离的 。
//一天内，可以将 任何单个 陆地单元（1）更改为水单元（0）。
//返回使陆地分离的最少天数。

//class TarjanSCC {
//private:
//    const vector<vector<int>>& edges;
//    vector<int> low, dfn, fa;
//    int timestamp = -1;
//    int n;
//
//private:
//    // Tarjan 算法求解割点模板
//    void getCuttingVertex(int u, int parent, vector<int>& ans) {
//        low[u] = dfn[u] = ++timestamp;
//        fa[u] = parent;
//        int child = 0;
//        bool iscv = false;
//        for (int v : edges[u]) {
//            if (dfn[v] == -1) {
//                ++child;
//                getCuttingVertex(v, u, ans);
//                low[u] = min(low[u], low[v]);
//                if (!iscv && parent != -1 && low[v] >= dfn[u]) {
//                    ans.push_back(u);
//                    iscv = true;
//                }
//            }
//            else if (v != fa[u]) {
//                low[u] = min(low[u], dfn[v]);
//            }
//        }
//        if (!iscv && parent == -1 && child >= 2) {
//            ans.push_back(u);
//        }
//    }
//
//public:
//    TarjanSCC(const vector<vector<int>>& _edges) : edges(_edges), n(_edges.size()) {}
//
//    int check() {
//        low.assign(n, -1);
//        dfn.assign(n, -1);
//        fa.assign(n, -1);
//        timestamp = -1;
//
//        // cutting vertices 存储割点
//        vector<int> cvs;
//        // connected components count 存储连通分量个数
//        int cccnt = 0;
//        for (int i = 0; i < n; ++i) {
//            if (dfn[i] == -1) {
//                ++cccnt;
//                getCuttingVertex(i, -1, cvs);
//            }
//        }
//        // 如果连通分量个数大于 1，答案为 0
//        if (cccnt > 1) {
//            return 0;
//        }
//        // 如果存在割点，答案为 1
//        if (!cvs.empty()) {
//            return 1;
//        }
//        return 2;
//    }
//};
//
//class Solution {
//private:
//    static constexpr int dirs[4][2] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };
//
//public:
//    int minDays(vector<vector<int>>& grid) {
//        int m = grid.size();
//        int n = grid[0].size();
//
//        // 节点重标号
//        int landCount = 0;
//        unordered_map<int, int> relabel;
//        for (int i = 0; i < m; ++i) {
//            for (int j = 0; j < n; ++j) {
//                if (grid[i][j] == 1) {
//                    relabel[i * n + j] = landCount;
//                    ++landCount;
//                }
//            }
//        }
//        if (!landCount) {
//            return 0;
//        }
//        if (landCount == 1) {
//            return 1;
//        }
//
//        // 添加图中的边
//        vector<vector<int>> edges(landCount);
//        for (int i = 0; i < m; ++i) {
//            for (int j = 0; j < n; ++j) {
//                if (grid[i][j] == 1) {
//                    for (int d = 0; d < 4; ++d) {
//                        int ni = i + dirs[d][0];
//                        int nj = j + dirs[d][1];
//                        if (ni >= 0 && ni < m && nj >= 0 && nj < n && grid[ni][nj] == 1) {
//                            edges[relabel[i * n + j]].push_back(relabel[ni * n + nj]);
//                        }
//                    }
//                }
//            }
//        }
//
//        auto scc = TarjanSCC(edges);
//        return scc.check();
//    }
//};

//LCP 54. 夺回据点

//欢迎各位勇者来到力扣城，本次试炼主题为「夺回据点」。
//魔物了占领若干据点，这些据点被若干条道路相连接，roads[i] = [x, y] 表示编号 x、y 的两个据点通过一条道路连接。
//现在勇者要将按照以下原则将这些据点逐一夺回：
//在开始的时候，勇者可以花费资源先夺回一些据点，初始夺回第 j 个据点所需消耗的资源数量为 cost[j]
//接下来，勇者在不消耗资源情况下，每次可以夺回一个和「已夺回据点」相连接的魔物据点，并对其进行夺回
//注：为了防止魔物暴动，勇者在每一次夺回据点后（包括花费资源夺回据点后），需要保证剩余的所有魔物据点之间是相连通的（不经过「已夺回据点」）。
//请返回勇者夺回所有据点需要消耗的最少资源数量。

//class Solution {
//    const int S = 0;
//    int n;
//
//    vector<vector<int>> e;
//    vector<int8_t> isCut;
//    vector<int> dfn, low;
//    int clk = 0;
//    stack<int> stk;
//    // 所有点双连通分量
//    vector<vector<int>> dcc;
//
//    void tarjan(int sn) {
//        dfn[sn] = low[sn] = ++clk;
//        stk.emplace(sn);
//        int flag = 0;
//        for (int fn : e[sn]) {
//            if (!dfn[fn]) {
//                tarjan(fn);
//                low[sn] = min(low[sn], low[fn]);
//                if (low[fn] >= dfn[sn]) {
//                    flag++;
//                    if (sn != S || flag > 1) isCut[sn] = true;
//                    int t;
//                    dcc.emplace_back(vector<int>());
//                    do {
//                        t = stk.top(); stk.pop();
//                        dcc.back().emplace_back(t);
//                    } while (t != fn);
//                    dcc.back().emplace_back(sn);
//                }
//            }
//            else low[sn] = min(low[sn], dfn[fn]);
//        }
//    }
//
//public:
//    long long minimumCost(vector<int>& cost, vector<vector<int>>& roads) {
//        n = cost.size();
//        if (n == 1) return cost[0];
//
//        e = vector<vector<int>>(n);
//        for (auto& r : roads) e[r[0]].emplace_back(r[1]), e[r[1]].emplace_back(r[0]);
//        isCut = vector<int8_t>(n);
//        dfn = low = vector<int>(n);
//        tarjan(S);
//
//        // 整张图是一个双连通分量，选择整张图权值最小的点即可
//        if (dcc.size() == 1) {
//            int ans = 2e9;
//            for (int x : cost) ans = min(ans, x);
//            return ans;
//        }
//
//        vector<int> vec;
//        for (auto& c : dcc) {
//            int cnt = 0, mn = 2e9;
//            for (int x : c) {
//                if (isCut[x]) cnt++;
//                else mn = min(mn, cost[x]);
//            }
//            // 该双连通分量只和一个割点相连，是缩点形成的树的叶子节点
//            if (cnt == 1) vec.emplace_back(mn);
//        }
//        ranges::sort(vec);
//        long long ans = 0;
//        for (int i = 0; i + 1 < vec.size(); i++) ans += vec[i];
//        return ans;
//    }
//};